package impl;

import anaydis.sort.SorterType;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class MergeSorterBottomUp extends AbstractSorter {

    public MergeSorterBottomUp() {
        super(SorterType.MERGE_BOTTOM_UP);
    }


    public <T> void sort(Comparator<T> comparator, List<T> list) {
        sort(comparator, list, 0, list.size() - 1);
    }

    private <T> void sort(Comparator<T> c, List<T> list, int l, int r) {
        if (r <= l) return;
        for (int m = 1; m <= r - l; m = m + m) {
            for (int i = l; i <= r - m; i += m + m) {
                sort(c, list, i, i + m - 1, min(i + m + m - 1, r));
            }
        }
    }

    private <T> void sort(Comparator<T> comparator, List<T> list, int left, int m, int right) {
        int i, j;
        List<T> aux = new ArrayList<T>();

        for (T t : list) {
            aux.add(t);
        }
        for (i = m + 1; i > left; i--) {
            aux.set(i - 1, list.get(i - 1));
        }
        for (j = m; j < right; j++) {
            aux.set(right + m - j, list.get(j + 1));
        }
        for (int k = left; k <= right; k++) {
            if (!greater(comparator, aux, j, i)) {
                list.set(k, aux.get(j--));
            } else {
                list.set(k, aux.get(i++));
            }
        }
    }

    private int min(int a, int b) {
        if (a < b) return a;
        return b;
    }
}
